package demo.DataStrucAndAlgo.AlgorithmOfTen;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Scanner;

/**
 * @Auther: hjy(lc))
 * @Date: 2022/8/9-08-09-19:13
 * @Description：demo.DataStrucAndAlgo.AlgorithmOfTen   最小生成树
 */
/*
Prim算法（普利姆算法）最小生成树MST
    最小生成树（MST）：给定一个带权的无向连通图，选取一颗生成树，使树上所有边上权的总和为最小。
 */
/*
如下图，有一个7村庄（A~G），需要修路将7个村庄连通，且不同路的路径不同（权值不同），要求既要连通7村，也要路径最短
    A~B 5    A~C 7   A~G 2
    B~G 3    B~D 9   E~F 5
    C~E 8    D~F 4   E~G 4
    F~G 6
    算法分析
        指定一个起点顶点，标记该顶点为已访问，将该顶点可能直连的顶点（未访问的）找到，然后根据连接顶点路径长度
    找到最短路径即可。在重复顶点个数的次数后，停止循环
*/
public class Prim {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int vertexOfNum = sc.nextInt();
        Graph graph = new Graph(vertexOfNum);
        ArrayList<Character> vertexs = new ArrayList<>(vertexOfNum);
        for (int i = 0; i < vertexOfNum; i++) {
            vertexs.add(sc.next().charAt(0));
        }
        char index1,index2;
        int[][] edges = new int[vertexOfNum][vertexOfNum];
        for (int i = 0; i < 10; i++) {      //保存无向权值
            index1 = sc.next().charAt(0);
            index2 = sc.next().charAt(0);
            int weight = sc.nextInt();
            edges[index1-'A'][index2-'A'] = weight;
            edges[index2-'A'][index1-'A'] = weight;

        }
        graph.setEdges(edges);
        graph.setVertexs(vertexs);


        System.out.println(prim(graph, vertexOfNum));
    }

    public static int prim(Graph graph,int vertexOfNum) {
        int weight = 0;
        graph.isVisited[0] = true;      //默认从一个顶点开始
        int A =0,B = 0;
        for (int k = 1; k < vertexOfNum; k++) {     //每一轮取离生成树权值最小的点
            int tempWeight = 10000;               //保存当前最小的权值
            for (int i = 0; i < vertexOfNum; i++) {     //
                if(!graph.isVisited[i]){            //如果未访问过，则跳过该顶点
                    continue;
                }
                for (int j = 0; j < vertexOfNum; j++) {
                    if(graph.isVisited[j]){        //如果访问过，则跳过该顶点
                        continue;
                    }
                    if(tempWeight > graph.getEdges()[i][j] && graph.getEdges()[i][j] != 0){            //更新最小权值
                        tempWeight = graph.getEdges()[i][j];
                        B = j;
                        A = i;
                    }
                }
            }
            graph.isVisited[B] = true;
            weight = weight + tempWeight;
            System.out.printf("%c -> %c 的权值：%d \n",(char)(A + 'A'),(char)(B + 'A'),tempWeight);
        }
        return weight;
    }
}
class Graph{
    private ArrayList<Character> vertexs;
    private int[][] edges;
    boolean[] isVisited;   //记录是否被访问过
    public Graph(int n) {
        vertexs = new ArrayList<>(n);
        isVisited = new boolean[n];
    }

    public ArrayList<Character> getVertexs() {
        return vertexs;
    }

    public void setVertexs(ArrayList<Character> vertexs) {
        this.vertexs = vertexs;
    }

    public int[][] getEdges() {
        return edges;
    }

    public void setEdges(int[][] edges) {
        this.edges = edges;
    }

    @Override
    public String toString() {
        return "Graph{" +
                "vertexs=" + vertexs +
                '}';
    }
}
